#include <iostream>
#include <string>
#include <vector>
using namespace std;
vector<pair<int, int>> pos{{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

void backtrace(vector<vector<char>> &board, int rows, int cols, string &word,
               int cur, int row, int col, bool &ok) {
  if (cur == word.size() - 1)
    ok = true;
  if (ok)
    return;
  char origin_char = board[row][col];
  board[row][col] = '#';
  for (auto &p : pos) {
    if (row + p.first >= 0 && row + p.first < rows && col + p.second >= 0 &&
        col + p.second < cols &&
        board[row + p.first][col + p.second] == word[cur + 1]) {
      char origin_char_t = board[row + p.first][col + p.second];
      board[row + p.first][col + p.second] = '#';
      backtrace(board, rows, cols, word, cur + 1, row + p.first, col + p.second,
                ok);
      board[row + p.first][col + p.second] = origin_char_t;
      if (ok) {
        return;
      }
    }
  }
  board[row][col] = origin_char;
}
bool exist(vector<vector<char>> &board, string word) {
  int rows = board.size();
  int cols = board[0].size();
  if (rows * cols < word.size()) {
    return false;
  }
  bool ok = false;
  // 记录已经走过的方块
  vector<vector<int>> stat(rows, vector<int>(cols, 0));
  for (int row = 0; row < rows; row++) {
    for (int col = 0; col < cols; col++) {
      if (board[row][col] == word[0]) {
        backtrace(board, rows, cols, word, 0, row, col, ok);
        if (ok) {
          return true;
        }
      }
    }
  }
  return false;
}

int main() {
  vector<vector<char>> board{
      {'A', 'B', 'C', 'E'}, {'S', 'F', 'C', 'S'}, {'A', 'D', 'E', 'E'}};
  cout << exist(board, "ABCB");
  return 0;
}